/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/contains-duplicate-ii
   @Language: C++
   @Datetime: 19-05-27 10:20
   */

class Solution {
public:
	/**
	 * @param nums: the given array
	 * @param k: the given number
	 * @return:  whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k
	 */
	bool containsNearbyDuplicate(vector<int> &nums, int k) {
		// Write your code here
		unordered_set<int> dict;
		for(int i=0; i<nums.size(); dict.insert(nums[i++])){
			if (dict.size()==k+1) dict.erase(nums[i-k-1]);
			if (dict.count(nums[i])) return true;
		}
		return false;
	}
};
